package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

public class _17_在二叉树中找一个节点的前驱后继节点 {


    public static TreeNode findPreNode(TreeNode node) {

        TreeNode preNode = node.left;

        if (preNode != null) {

            while (preNode.right != null) {

                preNode = preNode.right;
            }

            return preNode;
        }else {

            preNode = node.parent;
            while (preNode != null && preNode.left == node) {

                node = preNode;
                preNode = node.parent;
            }
        }

        return preNode;
    }

    public static TreeNode findNextNode(TreeNode node) {

        TreeNode nextNode = node.right;

        if (nextNode != null) {

            while (nextNode.left != null) {

                nextNode = nextNode.left;
            }
            return nextNode;
        }else {

            nextNode = node.parent;

            while (nextNode != null && nextNode.right == node) {

                node = nextNode;
                nextNode = node.parent;
            }

        }

        return nextNode;
    }

    public static void main(String[] args) {
        /**
         *                  6
         *
         *               3        8
         *
         *          1       4   9    10
         */
        TreeNode t1 = new TreeNode(6);
        t1.left = new TreeNode(3,t1);
        t1.left.left = new TreeNode(1,t1.left);
        t1.left.right = new TreeNode(4,t1.left);
        t1.right = new TreeNode(8,t1);
        t1.right.left = new TreeNode(9,t1.right);
        t1.right.right = new TreeNode(10,t1.right);

        TreeNode preNode = findPreNode(t1.left.right);
        System.out.println(preNode);
        System.out.println(findNextNode(t1.left));

    }

}
